/*
 * isBalanced.cpp
 *
 *  Created on: Jul 8, 2012
 *      Author: jh238d
 */

#include "BSTNode.h"
#include <iostream>
using namespace std;

/*Alter using iterative: In/Post order traversal, and track stack size*/
int treeHeight(BSTNode *root){
	if(!root) return 0;
	int leftHeight=treeHeight(root->left);
	int rightHeight=treeHeight(root->right);
	return max(leftHeight, rightHeight)+1;
}

bool isBalanced(BSTNode *root, int *depth){
	if(!root){
		*depth = 0;
		return true;
	}

	int left, right;
	if(isBalanced(root->left, &left)&&isBalanced(root->right, &right)){
		int diff = left - right;
		if(-1 <= diff && diff <= 1){
			*depth = ((left>right)?left:right)+1;
			return true;
		}
	}

	return false;
}

bool isBalanced(BSTNode *root){
	int depth = 0;
	return isBalanced(root, &depth);
}

